package likou.dtgh.beibao;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/09/03 22:28
 */

/**
 * 设有n种物品，每种物品有一个重量及一个价值。
 * 但每种物品的数量是无限的，同时有一个背包，最大载重量为M，
 * 今从n种物品中选取若干件同一种物品可以多次选取)，使其重量的和小于等于M，
 * 而价值的和为最大。
 */
public class _2 {
    public int getMax(int M, int[] W, int[] C) {
        int[] res = new int[M + 1];
        for (int i = 0; i < W.length; i++) {
            for (int j = M; j >= 1; j--) {
                for (int k=1;j<M/W[i];k++){
                    if (j>=k*W[i]){
                        res[j] = Math.max(res[j], res[j - k*W[i]] + k*C[i]);
                    }else {
                        break;
                    }
                }
            }
        }
        return res[M];
    }
}
